home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1995 July / macformat-026.iso / mac / Shareware City / Developers / berkeleydb1.73 / Berkeley_db / hash / hash_bigkey.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-27  |  16.0 KB  |  674 lines  |  [TEXT/MPS ]
  1. /*-
  2.  * Copyright (c) 1990, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Margo Seltzer.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)hash_bigkey.c    8.1 (Berkeley) 6/4/93";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #if defined(macintosh) && (defined(powerc) || defined(__powerc))
  42. #include "OurMalloc.h"
  43. #endif
  44.  
  45. /*
  46.  * PACKAGE: hash
  47.  * DESCRIPTION:
  48.  *    Big key/data handling for the hashing package.
  49.  *
  50.  * ROUTINES:
  51.  * External
  52.  *    __big_keydata
  53.  *    __big_split
  54.  *    __big_insert
  55.  *    __big_return
  56.  *    __big_delete
  57.  *    __find_last_page
  58.  * Internal
  59.  *    collect_key
  60.  *    collect_data
  61.  */
  62.  
  63. #include <sys/param.h>
  64.  
  65. #include <errno.h>
  66. #include <stdio.h>
  67. #include <stdlib.h>
  68. #include <string.h>
  69.  
  70. #ifdef DEBUG
  71. #include <assert.h>
  72. #endif
  73.  
  74. #include <db.h>
  75. #include "hash.h"
  76. #include "page.h"
  77. #include "extern.h"
  78.  
  79. static int collect_key __P((HTAB *, BUFHEAD *, int, DBT *, int));
  80. static int collect_data __P((HTAB *, BUFHEAD *, int, int));
  81.  
  82. /*
  83.  * Big_insert
  84.  *
  85.  * You need to do an insert and the key/data pair is too big
  86.  *
  87.  * Returns:
  88.  * 0 ==> OK
  89.  *-1 ==> ERROR
  90.  */
  91. extern int
  92. __big_insert(hashp, bufp, key, val)
  93.     HTAB *hashp;
  94.     BUFHEAD *bufp;
  95.     const DBT *key, *val;
  96. {
  97.     register u_short *p;
  98.     int key_size, n, val_size;
  99.     u_short space, move_bytes, off;
  100.     char *cp, *key_data, *val_data;
  101.  
  102.     cp = bufp->page;        /* Character pointer of p. */
  103.     p = (u_short *)cp;
  104.  
  105.     key_data = (char *)key->data;
  106.     key_size = key->size;
  107.     val_data = (char *)val->data;
  108.     val_size = val->size;
  109.  
  110.     /* First move the Key */
  111.     for (space = FREESPACE(p) - BIGOVERHEAD; key_size;
  112.         space = FREESPACE(p) - BIGOVERHEAD) {
  113.         move_bytes = MIN(space, key_size);
  114.         off = OFFSET(p) - move_bytes;
  115.         memmove(cp + off, key_data, move_bytes);
  116.         key_size -= move_bytes;
  117.         key_data += move_bytes;
  118.         n = p[0];
  119.         p[++n] = off;
  120.         p[0] = ++n;
  121.         FREESPACE(p) = off - PAGE_META(n);
  122.         OFFSET(p) = off;
  123.         p[n] = PARTIAL_KEY;
  124.         bufp = __add_ovflpage(hashp, bufp);
  125.         if (!bufp)
  126.             return (-1);
  127.         n = p[0];
  128.         if (!key_size)
  129.             if (FREESPACE(p)) {
  130.                 move_bytes = MIN(FREESPACE(p), val_size);
  131.                 off = OFFSET(p) - move_bytes;
  132.                 p[n] = off;
  133.                 memmove(cp + off, val_data, move_bytes);
  134.                 val_data += move_bytes;
  135.                 val_size -= move_bytes;
  136.                 p[n - 2] = FULL_KEY_DATA;
  137.                 FREESPACE(p) = FREESPACE(p) - move_bytes;
  138.                 OFFSET(p) = off;
  139.             } else
  140.                 p[n - 2] = FULL_KEY;
  141.         p = (u_short *)bufp->page;
  142.         cp = bufp->page;
  143.         bufp->flags |= BUF_MOD;
  144.     }
  145.  
  146.     /* Now move the data */
  147.     for (space = FREESPACE(p) - BIGOVERHEAD; val_size;
  148.         space = FREESPACE(p) - BIGOVERHEAD) {
  149.         move_bytes = MIN(space, val_size);
  150.         /*
  151.          * Here's the hack to make sure that if the data ends on the
  152.          * same page as the key ends, FREESPACE is at least one.
  153.          */
  154.         if (space == val_size && val_size == val->size)
  155.             move_bytes--;
  156.         off = OFFSET(p) - move_bytes;
  157.         memmove(cp + off, val_data, move_bytes);
  158.         val_size -= move_bytes;
  159.         val_data += move_bytes;
  160.         n = p[0];
  161.         p[++n] = off;
  162.         p[0] = ++n;
  163.         FREESPACE(p) = off - PAGE_META(n);
  164.         OFFSET(p) = off;
  165.         if (val_size) {
  166.             p[n] = FULL_KEY;
  167.             bufp = __add_ovflpage(hashp, bufp);
  168.             if (!bufp)
  169.                 return (-1);
  170.             cp = bufp->page;
  171.             p = (u_short *)cp;
  172.         } else
  173.             p[n] = FULL_KEY_DATA;
  174.         bufp->flags |= BUF_MOD;
  175.     }
  176.     return (0);
  177. }
  178.  
  179. /*
  180.  * Called when bufp's page  contains a partial key (index should be 1)
  181.  *
  182.  * All pages in the big key/data pair except bufp are freed.  We cannot
  183.  * free bufp because the page pointing to it is lost and we can't get rid
  184.  * of its pointer.
  185.  *
  186.  * Returns:
  187.  * 0 => OK
  188.  *-1 => ERROR
  189.  */
  190. extern int
  191. __big_delete(hashp, bufp)
  192.     HTAB *hashp;
  193.     BUFHEAD *bufp;
  194. {
  195.     register BUFHEAD *last_bfp, *rbufp;
  196.     u_short *bp, pageno;
  197.     int key_done, n;
  198.  
  199.     rbufp = bufp;
  200.     last_bfp = NULL;
  201.     bp = (u_short *)bufp->page;
  202.     pageno = 0;
  203.     key_done = 0;
  204.  
  205.     while (!key_done || (bp[2] != FULL_KEY_DATA)) {
  206.         if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA)
  207.             key_done = 1;
  208.  
  209.         /*
  210.          * If there is freespace left on a FULL_KEY_DATA page, then
  211.          * the data is short and fits entirely on this page, and this
  212.          * is the last page.
  213.          */
  214.         if (bp[2] == FULL_KEY_DATA && FREESPACE(bp))
  215.             break;
  216.         pageno = bp[bp[0] - 1];
  217.         rbufp->flags |= BUF_MOD;
  218.         rbufp = __get_buf(hashp, pageno, rbufp, 0);
  219.         if (last_bfp)
  220.             __free_ovflpage(hashp, last_bfp);
  221.         last_bfp = rbufp;
  222.         if (!rbufp)
  223.             return (-1);        /* Error. */
  224.         bp = (u_short *)rbufp->page;
  225.     }
  226.  
  227.     /*
  228.      * If we get here then rbufp points to the last page of the big
  229.      * key/data pair.  Bufp points to the first one -- it should now be
  230.      * empty pointing to the next page after this pair.  Can't free it
  231.      * because we don't have the page pointing to it.
  232.      */
  233.  
  234.     /* This is information from the last page of the pair. */
  235.     n = bp[0];
  236.     pageno = bp[n - 1];
  237.  
  238.     /* Now, bp is the first page of the pair. */
  239.     bp = (u_short *)bufp->page;
  240.     if (n > 2) {
  241.         /* There is an overflow page. */
  242.         bp[1] = pageno;
  243.         bp[2] = OVFLPAGE;
  244.         bufp->ovfl = rbufp->ovfl;
  245.     } else
  246.         /* This is the last page. */
  247.         bufp->ovfl = NULL;
  248.     n -= 2;
  249.     bp[0] = n;
  250.     FREESPACE(bp) = hashp->BSIZE - PAGE_META(n);
  251.     OFFSET(bp) = hashp->BSIZE - 1;
  252.  
  253.     bufp->flags |= BUF_MOD;
  254.     if (rbufp)
  255.         __free_ovflpage(hashp, rbufp);
  256.     if (last_bfp != rbufp)
  257.         __free_ovflpage(hashp, last_bfp);
  258.  
  259.     hashp->NKEYS--;
  260.     return (0);
  261. }
  262. /*
  263.  * Returns:
  264.  *  0 = key not found
  265.  * -1 = get next overflow page
  266.  * -2 means key not found and this is big key/data
  267.  * -3 error
  268.  */
  269. extern int
  270. __find_bigpair(hashp, bufp, ndx, key, size)
  271.     HTAB *hashp;
  272.     BUFHEAD *bufp;
  273.     int ndx;
  274.     char *key;
  275.     int size;
  276. {
  277.     register u_short *bp;
  278.     register char *p;
  279.     int ksize;
  280.     u_short bytes;
  281.     char *kkey;
  282.  
  283.     bp = (u_short *)bufp->page;
  284.     p = bufp->page;
  285.     ksize = size;
  286.     kkey = key;
  287.  
  288.     for (bytes = hashp->BSIZE - bp[ndx];
  289.         bytes <= size && bp[ndx + 1] == PARTIAL_KEY;
  290.         bytes = hashp->BSIZE - bp[ndx]) {
  291.         if (memcmp(p + bp[ndx], kkey, bytes))
  292.             return (-2);
  293.         kkey += bytes;
  294.         ksize -= bytes;
  295.         bufp = __get_buf(hashp, bp[ndx + 2], bufp, 0);
  296.         if (!bufp)
  297.             return (-3);
  298.         p = bufp->page;
  299.         bp = (u_short *)p;
  300.         ndx = 1;
  301.     }
  302.  
  303.     if (bytes != ksize || memcmp(p + bp[ndx], kkey, bytes)) {
  304. #ifdef HASH_STATISTICS
  305.         ++hash_collisions;
  306. #endif
  307.         return (-2);
  308.     } else
  309.         return (ndx);
  310. }
  311.  
  312. /*
  313.  * Given the buffer pointer of the first overflow page of a big pair,
  314.  * find the end of the big pair
  315.  *
  316.  * This will set bpp to the buffer header of the last page of the big pair.
  317.  * It will return the pageno of the overflow page following the last page
  318.  * of the pair; 0 if there isn't any (i.e. big pair is the last key in the
  319.  * bucket)
  320.  */
  321. extern u_short
  322. __find_last_page(hashp, bpp)
  323.     HTAB *hashp;
  324.     BUFHEAD **bpp;
  325. {
  326.     BUFHEAD *bufp;
  327.     u_short *bp, pageno;
  328.     int n;
  329.  
  330.     bufp = *bpp;
  331.     bp = (u_short *)bufp->page;
  332.     for (;;) {
  333.         n = bp[0];
  334.  
  335.         /*
  336.          * This is the last page if: the tag is FULL_KEY_DATA and
  337.          * either only 2 entries OVFLPAGE marker is explicit there
  338.          * is freespace on the page.
  339.          */
  340.         if (bp[2] == FULL_KEY_DATA &&
  341.             ((n == 2) || (bp[n] == OVFLPAGE) || (FREESPACE(bp))))
  342.             break;
  343.  
  344.         pageno = bp[n - 1];
  345.         bufp = __get_buf(hashp, pageno, bufp, 0);
  346.         if (!bufp)
  347.             return (0);    /* Need to indicate an error! */
  348.         bp = (u_short *)bufp->page;
  349.     }
  350.  
  351.     *bpp = bufp;
  352.     if (bp[0] > 2)
  353.         return (bp[3]);
  354.     else
  355.         return (0);
  356. }
  357.  
  358. /*
  359.  * Return the data for the key/data pair that begins on this page at this
  360.  * index (index should always be 1).
  361.  */
  362. extern int
  363. __big_return(hashp, bufp, ndx, val, set_current)
  364.     HTAB *hashp;
  365.     BUFHEAD *bufp;
  366.     int ndx;
  367.     DBT *val;
  368.     int set_current;
  369. {
  370.     BUFHEAD *save_p;
  371.     u_short *bp, len, off, save_addr;
  372.     char *tp;
  373.  
  374.     bp = (u_short *)bufp->page;
  375.     while (bp[ndx + 1] == PARTIAL_KEY) {
  376.         bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  377.         if (!bufp)
  378.             return (-1);
  379.         bp = (u_short *)bufp->page;
  380.         ndx = 1;
  381.     }
  382.  
  383.     if (bp[ndx + 1] == FULL_KEY) {
  384.         bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  385.         if (!bufp)
  386.             return (-1);
  387.         bp = (u_short *)bufp->page;
  388.         save_p = bufp;
  389.         save_addr = save_p->addr;
  390.         off = bp[1];
  391.         len = 0;
  392.     } else
  393.         if (!FREESPACE(bp)) {
  394.             /*
  395.              * This is a hack.  We can't distinguish between
  396.              * FULL_KEY_DATA that contains complete data or
  397.              * incomplete data, so we require that if the data
  398.              * is complete, there is at least 1 byte of free
  399.              * space left.
  400.              */
  401.             off = bp[bp[0]];
  402.             len = bp[1] - off;
  403.             save_p = bufp;
  404.             save_addr = bufp->addr;
  405.             bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  406.             if (!bufp)
  407.                 return (-1);
  408.             bp = (u_short *)bufp->page;
  409.         } else {
  410.             /* The data is all on one page. */
  411.             tp = (char *)bp;
  412.             off = bp[bp[0]];
  413.             val->data = (u_char *)tp + off;
  414.             val->size = bp[1] - off;
  415.             if (set_current) {
  416.                 if (bp[0] == 2) {    /* No more buckets in
  417.                              * chain */
  418.                     hashp->cpage = NULL;
  419.                     hashp->cbucket++;
  420.                     hashp->cndx = 1;
  421.                 } else {
  422.                     hashp->cpage = __get_buf(hashp,
  423.                         bp[bp[0] - 1], bufp, 0);
  424.                     if (!hashp->cpage)
  425.                         return (-1);
  426.                     hashp->cndx = 1;
  427.                     if (!((u_short *)
  428.                         hashp->cpage->page)[0]) {
  429.                         hashp->cbucket++;
  430.                         hashp->cpage = NULL;
  431.                     }
  432.                 }
  433.             }
  434.             return (0);
  435.         }
  436.  
  437.     val->size = collect_data(hashp, bufp, (int)len, set_current);
  438.     if (val->size == -1)
  439.         return (-1);
  440.     if (save_p->addr != save_addr) {
  441.         /* We are pretty short on buffers. */
  442.         errno = EINVAL;            /* OUT OF BUFFERS */
  443.         return (-1);
  444.     }
  445.     memmove(hashp->tmp_buf, (save_p->page) + off, len);
  446.     val->data = (u_char *)hashp->tmp_buf;
  447.     return (0);
  448. }
  449. /*
  450.  * Count how big the total datasize is by recursing through the pages.  Then
  451.  * allocate a buffer and copy the data as you recurse up.
  452.  */
  453. static int
  454. collect_data(hashp, bufp, len, set)
  455.     HTAB *hashp;
  456.     BUFHEAD *bufp;
  457.     int len, set;
  458. {
  459.     register u_short *bp;
  460.     register char *p;
  461.     BUFHEAD *xbp;
  462.     u_short save_addr;
  463.     int mylen, totlen;
  464.  
  465.     p = bufp->page;
  466.     bp = (u_short *)p;
  467.     mylen = hashp->BSIZE - bp[1];
  468.     save_addr = bufp->addr;
  469.  
  470.     if (bp[2] == FULL_KEY_DATA) {        /* End of Data */
  471.         totlen = len + mylen;
  472.         if (hashp->tmp_buf)
  473.             free(hashp->tmp_buf);
  474.         hashp->tmp_buf = malloc(totlen);
  475.         if (!hashp->tmp_buf)
  476.             return (-1);
  477.         if (set) {
  478.             hashp->cndx = 1;
  479.             if (bp[0] == 2) {    /* No more buckets in chain */
  480.                 hashp->cpage = NULL;
  481.                 hashp->cbucket++;
  482.             } else {
  483.                 hashp->cpage =
  484.                     __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  485.                 if (!hashp->cpage)
  486.                     return (-1);
  487.                 else if (!((u_short *)hashp->cpage->page)[0]) {
  488.                     hashp->cbucket++;
  489.                     hashp->cpage = NULL;
  490.                 }
  491.             }
  492.         }
  493.     } else {
  494.         xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  495.         if (!xbp || ((totlen =
  496.             collect_data(hashp, xbp, len + mylen, set)) < 1))
  497.             return (-1);
  498.     }
  499.     if (bufp->addr != save_addr) {
  500.         errno = EINVAL;            /* Out of buffers. */
  501.         return (-1);
  502.     }
  503.     memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], mylen);
  504.     return (totlen);
  505. }
  506.  
  507. /*
  508.  * Fill in the key and data for this big pair.
  509.  */
  510. extern int
  511. __big_keydata(hashp, bufp, key, val, set)
  512.     HTAB *hashp;
  513.     BUFHEAD *bufp;
  514.     DBT *key, *val;
  515.     int set;
  516. {
  517.     key->size = collect_key(hashp, bufp, 0, val, set);
  518.     if (key->size == -1)
  519.         return (-1);
  520.     key->data = (u_char *)hashp->tmp_key;
  521.     return (0);
  522. }
  523.  
  524. /*
  525.  * Count how big the total key size is by recursing through the pages.  Then
  526.  * collect the data, allocate a buffer and copy the key as you recurse up.
  527.  */
  528. static int
  529. collect_key(hashp, bufp, len, val, set)
  530.     HTAB *hashp;
  531.     BUFHEAD *bufp;
  532.     int len;
  533.     DBT *val;
  534.     int set;
  535. {
  536.     BUFHEAD *xbp;
  537.     char *p;
  538.     int mylen, totlen;
  539.     u_short *bp, save_addr;
  540.  
  541.     p = bufp->page;
  542.     bp = (u_short *)p;
  543.     mylen = hashp->BSIZE - bp[1];
  544.  
  545.     save_addr = bufp->addr;
  546.     totlen = len + mylen;
  547.     if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) {    /* End of Key. */
  548.         if (hashp->tmp_key)
  549.             free(hashp->tmp_key);
  550.         hashp->tmp_key = malloc(totlen);
  551.         if (!hashp->tmp_key)
  552.             return (-1);
  553.         if (__big_return(hashp, bufp, 1, val, set))
  554.             return (-1);
  555.     } else {
  556.         xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  557.         if (!xbp || ((totlen =
  558.             collect_key(hashp, xbp, totlen, val, set)) < 1))
  559.             return (-1);
  560.     }
  561.     if (bufp->addr != save_addr) {
  562.         errno = EINVAL;        /* MIS -- OUT OF BUFFERS */
  563.         return (-1);
  564.     }
  565.     memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], mylen);
  566.     return (totlen);
  567. }
  568.  
  569. /*
  570.  * Returns:
  571.  *  0 => OK
  572.  * -1 => error
  573.  */
  574. extern int
  575. __big_split(hashp, op, np, big_keyp, addr, obucket, ret)
  576.     HTAB *hashp;
  577.     BUFHEAD *op;    /* Pointer to where to put keys that go in old bucket */
  578.     BUFHEAD *np;    /* Pointer to new bucket page */
  579.             /* Pointer to first page containing the big key/data */
  580.     BUFHEAD *big_keyp;
  581.     int addr;    /* Address of big_keyp */
  582.     u_int   obucket;/* Old Bucket */
  583.     SPLIT_RETURN *ret;
  584. {
  585.     register BUFHEAD *tmpp;
  586.     register u_short *tp;
  587.     BUFHEAD *bp;
  588.     DBT key, val;
  589.     u_int change;
  590.     u_short free_space, n, off;
  591.  
  592.     bp = big_keyp;
  593.  
  594.     /* Now figure out where the big key/data goes */
  595.     if (__big_keydata(hashp, big_keyp, &key, &val, 0))
  596.         return (-1);
  597.     change = (__call_hash(hashp, key.data, key.size) != obucket);
  598.  
  599.     if (ret->next_addr = __find_last_page(hashp, &big_keyp)) {
  600.         if (!(ret->nextp =
  601.             __get_buf(hashp, ret->next_addr, big_keyp, 0)))
  602.             return (-1);;
  603.     } else
  604.         ret->nextp = NULL;
  605.  
  606.     /* Now make one of np/op point to the big key/data pair */
  607. #ifdef DEBUG
  608.     assert(np->ovfl == NULL);
  609. #endif
  610.     if (change)
  611.         tmpp = np;
  612.     else
  613.         tmpp = op;
  614.  
  615.     tmpp->flags |= BUF_MOD;
  616. #ifdef DEBUG1
  617.     (void)fprintf(stderr,
  618.         "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr,
  619.         (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0));
  620. #endif
  621.     tmpp->ovfl = bp;    /* one of op/np point to big_keyp */
  622.     tp = (u_short *)tmpp->page;
  623. #ifdef DEBUG
  624.     assert(FREESPACE(tp) >= OVFLSIZE);
  625. #endif
  626.     n = tp[0];
  627.     off = OFFSET(tp);
  628.     free_space = FREESPACE(tp);
  629.     tp[++n] = (u_short)addr;
  630.     tp[++n] = OVFLPAGE;
  631.     tp[0] = n;
  632.     OFFSET(tp) = off;
  633.     FREESPACE(tp) = free_space - OVFLSIZE;
  634.  
  635.     /*
  636.      * Finally, set the new and old return values. BIG_KEYP contains a
  637.      * pointer to the last page of the big key_data pair. Make sure that
  638.      * big_keyp has no following page (2 elements) or create an empty
  639.      * following page.
  640.      */
  641.  
  642.     ret->newp = np;
  643.     ret->oldp = op;
  644.  
  645.     tp = (u_short *)big_keyp->page;
  646.     big_keyp->flags |= BUF_MOD;
  647.     if (tp[0] > 2) {
  648.         /*
  649.          * There may be either one or two offsets on this page.  If
  650.          * there is one, then the overflow page is linked on normally
  651.          * and tp[4] is OVFLPAGE.  If there are two, tp[4] contains
  652.          * the second offset and needs to get stuffed in after the
  653.          * next overflow page is added.
  654.          */
  655.         n = tp[4];
  656.         free_space = FREESPACE(tp);
  657.         off = OFFSET(tp);
  658.         tp[0] -= 2;
  659.         FREESPACE(tp) = free_space + OVFLSIZE;
  660.         OFFSET(tp) = off;
  661.         tmpp = __add_ovflpage(hashp, big_keyp);
  662.         if (!tmpp)
  663.             return (-1);
  664.         tp[4] = n;
  665.     } else
  666.         tmpp = big_keyp;
  667.  
  668.     if (change)
  669.         ret->newp = tmpp;
  670.     else
  671.         ret->oldp = tmpp;
  672.     return (0);
  673. }
  674.